752. Open the Lock
Medium

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

 

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1

 

Constraints:

  • 1 <= deadends.length <= 500
  • deadends[i].length == 4
  • target.length == 4
  • target will not be in the list deadends.
  • target and deadends[i] consist of digits only.
Accepted
118.2K
Submissions
215.9K
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
We can think of this problem as a shortest path problem on a graph: there are `10000` nodes (strings `'0000'` to `'9999'`), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so `'0'` and `'9'` differ by 1), and if *both* nodes are not in `deadends`.

Average Rating: 4.16 (57 votes)

Premium

Approach #1: Breadth-First Search [Accepted]

Intuition

We can think of this problem as a shortest path problem on a graph: there are 10000 nodes (strings '0000' to '9999'), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so '0' and '9' differ by 1), and if both nodes are not in deadends.

Algorithm

To solve a shortest path problem, we use a breadth-first search. The basic structure uses a Queue queue plus a Set seen that records if a node has ever been enqueued. This pushes all the work to the neighbors function - in our Python implementation, all the code after while queue: is template code, except for if node in dead: continue.

As for the neighbors function, for each position in the lock i = 0, 1, 2, 3, for each of the turns d = -1, 1, we determine the value of the lock after the i-th wheel has been turned in the direction d.

Care should be taken in our algorithm, as the graph does not have an edge unless both nodes are not in deadends. If our neighbors function checks only the target for being in deadends, we also need to check whether '0000' is in deadends at the beginning. In our implementation, we check at the visitor level so as to neatly handle this problem in all cases.

In Java, our implementation also inlines the neighbors function for convenience, and uses null inputs in the queue to represent a layer change. When the layer changes, we depth++ our global counter, and queue.peek() != null checks if there are still nodes enqueued.

Complexity Analysis

  • Time Complexity: O(N2AN+D)O(N^2 * \mathcal{A}^N + D) where A\mathcal{A} is the number of digits in our alphabet, NN is the number of digits in the lock, and DD is the size of deadends. We might visit every lock combination, plus we need to instantiate our set dead. When we visit every lock combination, we spend O(N2)O(N^2) time enumerating through and constructing each node.

  • Space Complexity: O(AN+D)O(\mathcal{A}^N + D), for the queue and the set dead.

Report Article Issue

Comments: 28
meetul's avatar
Read More

Complexity: O(N^2 * A^N + D)
where, N is Number of dials (4 in our case)
A is number of alphabets (10 in our case -> 0 to 9)
D is the size of deadends.

There are 10 x 10 x 10 x 10 possible combinations => 10^4 => A^N
For each combination, we are looping 4 times (which is N) and in each iteration, there are substring operations ( which is O(N) * constant) => O(4N*constant) => O(4N) => O(NN) => O(N^2)
Total complexity => A^N * N^2, plus D to create the hashset => N^2 * A^N + D

53
Show 3 replies
Reply
Share
Report
pranav89's avatar
Read More

Yeah, where N is the length of lock (4 in our case):

  • O(N) for enumerating neighbors,
  • O(digits^N) (10^4 in this case neighbors for each node)
  • O(D) for initializing deadends set

So time complexity is O(N*digits^N + D)

52
Show 1 reply
Reply
Share
Report
ArizonaTea's avatar
Read More

The time for enumerating the neighbors of each node is O(2N) which is O(N) not O(N^2). Just go through each digit with exploring digit+1 and digit-1.

58
Show 2 replies
Reply
Share
Report
spirit_room's avatar
Read More

dead and seen can be united as one set actually for simplicity.

23
Show 3 replies
Reply
Share
Report
harmanpatial's avatar
Read More

Given the search space it would be better if we did double sided BFS -- layer by layer BFS from "0000" and the target.

12
Show 1 reply
Reply
Share
Report
undefitied's avatar
Read More

I guess I seem to feel some sort of disarmed with problems that require thinking "oh, here I will just do 10000 combinations for the number of 4 elements"...

10
Reply
Share
Report
solomencevs's avatar
Read More

Inserting null as a delimiter between layers is smart approach and allows to avoid storing depth for each element of the queue. However, as Queue JavaDoc states, "Even in the implementations that permit it, null should not be inserted into a Queue".

5
Show 2 replies
Reply
Share
Report
tarxvzf's avatar
Read More

Problems like these are good candidates for A* search rather than BFS since you can easily calculate the admissible heuristic as the Manhattan distance to the target.

2
Show 2 replies
Reply
Share
Report
tommym's avatar
Read More

for the time complexity, where does the N^2 come from?

2
Show 1 reply
Reply
Share
Report
palaska's avatar
Read More

This solution is actually slow (runs in 126ms in my trial). Instead of a breadth-first search, it is much better to use a directed approach like A*. You can check out my 23ms solution here: https://leetcode.com/problems/open-the-lock/discuss/289516/My-23ms-A*-Java-solution-using-a-priority-queue-(beats-96)

2
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/04/2021 19:28Accepted840 ms75.5 MBcpp
09/28/2020 08:58Accepted892 ms70.8 MBcpp
/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium
Previous submission loaded successfully.